package com.sukaiyi.leetcode._4median_of_two_sorted_arrays;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * 寻找两个正序数组的中位数
 * <p>
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * 你可以假设 nums1 和 nums2 不会同时为空。
 *
 * @author sukaiyi
 * @date 2020/08/25
 * @see <a href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/">题目地址</a>
 */
public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int cnts1 = nums1.length;
        int cnts2 = nums2.length;
        int cnt = cnts1 + cnts2;
        int half = cnt / 2;
        int passed = 0, i = 0, j = 0;
        Integer passedNum1 = null, passedNum2 = null;
        while (passed <= half) {
            passed++;
            if (j >= cnts2 && i < cnts1 || i < cnts1 && nums1[i] < nums2[j]) {
                passedNum2 = passedNum1;
                passedNum1 = nums1[i++];
            } else if (j < cnts2) {
                passedNum2 = passedNum1;
                passedNum1 = nums2[j++];
            }
        }
        if (passedNum2 == null) {
            return passedNum1;
        }
        if (cnt % 2 == 0) {
            return (passedNum2 + passedNum1) / 2.0;
        } else {
            return Math.max(passedNum2, passedNum1);
        }
    }

    @Test
    public void testCase() {
        Assertions.assertEquals(1.5, findMedianSortedArrays(new int[]{}, new int[]{1, 2}));
        Assertions.assertEquals(2.0, findMedianSortedArrays(new int[]{99}, new int[]{1, 2}));
        Assertions.assertEquals(1.5, findMedianSortedArrays(new int[]{2}, new int[]{1}));
        Assertions.assertEquals(2.0, findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));
        Assertions.assertEquals(2.5, findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4}));
    }

}
